
\section{Fingerprinting}
\label{wififingerprinting}
Wi-Fi is a widespread technology and is deployed at most offices, homes, and public buildings.
It is used in indoor positioning systems \cite{mlws,5388848,radarlf,Bell2010,6068444} and provides a low installation cost as no extra infrastructure requirements are needed. 
If Wi-Fi signals propagated trough space, such that distance to the emitter and the receiver is correlated, utilizing Wi-Fi to determine a devices position would be trivial~\cite{ariadne2006}. 
The location of an object can be found by having a minimum of three Wi-Fi radios with known positions. 
Finding the objects position is a matter of solving a quadratic equation with two unknowns.  
Unfortunately Wi-Fi signals are greatly affected by building interior, people moving trough the space, humidity, and other factors making it non-trivial to use for location based services~\cite{6068444}.
It is expected that using solely Wi-Fi gives an estimation accuracy between 2 to 10 meters~\cite{6068444,mlws}

A class of techniques which can utilizes Wi-Fi is the \textit{Location Fingerprinting}(LF) techniques~\cite{taxonomy2007}. 
An LF technique is divided into two phases. 
An initial phases, called the offline phase, in which a \textit{radio map} is created and a second phase where the radio map is used to estimate the device's location.
The two phases are elaborated in the following two sections. 

\subsection{Generating a Radio Map}
\label{sub:radiomap}
A radio map can be created using either an empirical or a model-based approach~\cite{taxonomy2007}. 
A model-based approach uses parametrized model for LF based on the building layout and a theoretical propagation model~\cite{radarlf}.   
Empirical methods can be subdivided into probabilistic and deterministic models.  
Both use measured data, known as fingerprints, often collected by researchers wandering around the area to be mapped with a laptop performing measurements~\cite{roblocal2004,5388848, radarlf}.  
Deterministic models treat the measured fingerprints as single values while probabilistic methods represent data as probability models. 
Both empirical methods can be divided into interpolating and aggregating methods. 
Aggregating methods combine measured values into mean values in the radio map~\cite{radarlf, roblocal2004}, while interpolating methods creates new data points by interpolating existing data points~\cite{locadio2004}. 
Deterministic models utilize direct-methods where fingerprint data are used without any further processing or with outliers removed, as in~\cite{1200692}. 

\subsection{Estimating Positions}
Methods for estimating the position of the tracked device are, as empirical methods for radio map generation, divided into the two subcategories: deterministic and probabilistic~\cite{taxonomy2007}.
There are several deterministic methods, but most is variations to NN or KNN algorithms as
the nearest neighbour in signal space method (NNSS)
described in~\cite{6068444} and \cite{radarlf}.
Assume that there are $n$ Wi-Fi points in the indoor space of interest and $m$ of those are pre-selected as reference points. 
A signal measure or fingerprint is then an $n$-dimensional vector $s=(s_{1},\dots,s_{n})$ and $s_{i} (1 \le  i \le n)$ denotes the signal strength from the $i$-th Wi-Fi radio. 
The distance is calculated as euclidean distance the current signal measure (query) $q$ and each measured fingerprint $s^{j} (1 \le j \le m)$, 
that is $dist(q,s^{j}) = \sqrt{\sum_{i=1}^{n}\left(q_{i}-s^{j}_{i}\right)}$ 
given a radio map and a user signal strength measure, the location can be found by searching the radio map. 
If there is an exact match the user is at this location otherwise NN query can be used.
As described in~\cite{ariadne2006} using KNN is preferred to single NN as the query point is often close too two or more radio map entries.
Probabilistic methods include hidden Markov Chains and Center of Mass~\cite{Youssef2005}.

 






